home *** CD-ROM | disk | FTP | other *** search
/ Mac Mania 6 / MacMania 6.toast / / Tools&Utilities / EnterAct Stuff / hAWK project / AWK Source / hAWK_Sort.c < prev    next >
Text File  |  1994-12-22  |  9KB  |  331 lines
  1. /* hAWK_Sort.c : builtin sort capability */
  2. /* Copyright © 1986, 1988, 1989 1991 the Free Software Foundation, Inc.
  3.  *         This file is part of GAWK, the GNU implementation of the
  4.  * AWK Progamming Language, modified for the Macintosh (also called hAWK).
  5.  *         GAWK is free software; you can redistribute or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 1, or any later version.
  8.  *         GAWK is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11.  * GNU General Public License for more details.
  12.  *         You should have received a copy of the GNU General Public License
  13.  * along with GAWK; see the file "COPYING hAWK". If not, write to
  14.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  15.  * Written for THINK C 4 on the Macintosh by Ken Earle (Dynabyte) Aug 1991.
  16.  */
  17. #include "AWK.H"
  18.  
  19. enum {ASCII_SORT, RASCII_SORT, DICT_SORT, RDICT_SORT, 
  20.     NUM_SORT, RNUM_SORT, roentiyehs = 999};
  21. #define NUMSORTS    6
  22.  
  23. /* from ARRAY.C */
  24. extern void assoc_clear(NODE *symbol);
  25. extern struct search *assoc_scan_sort(NODE *symbol);
  26. extern struct search *assoc_next_sort(struct search *lookat);
  27.  
  28. /* hAWK_Sort.c functions */
  29. short b_get_three(NODE *tree, NODE **res1, NODE **res2, NODE **res3);
  30. NODE *do_sort(NODE *tree);
  31. static long create_index_array(NODE *arr, NODE *ind, short sort_type);
  32. void InitCompFuncArray(void);
  33. void SortArray(long numIndexes, short sort_type);
  34. void qs(long lb, long ub);
  35. long Rearrange(long lb, long ub);
  36. void SwapSorters(long i, long j);
  37. /* comparison functions */
  38. short ASCIIComp(long i, long j);
  39. short RASCIIComp(long i, long j);
  40. short DictComp(long i, long j);
  41. short RDictComp(long i, long j);
  42. short NumComp(long i, long j);
  43. short RNumComp(long i, long j);
  44. short PtrLenPtrLenCompare(Ptr spatPtr, short patLen, Ptr stargetPtr, short targetLen);
  45.  
  46.  
  47. short b_get_three(NODE *tree, NODE **res1, NODE **res2, NODE **res3)
  48. {
  49.     if (!tree) {
  50.         return 0;
  51.     }
  52.     *res1 = tree->lnode;
  53.     if (!tree->rnode)
  54.         return 1;
  55.     tree = tree->rnode;
  56.     *res2 = tree->lnode;
  57.     if (!tree->rnode)
  58.         return 2;
  59.     tree = tree->rnode;
  60.     *res3 = tree_eval(tree->lnode);
  61.     return 3;
  62. }
  63.  
  64. NODE *do_sort(NODE *tree)
  65.     {
  66.     NODE     *t1, *t2, *t3;    /* array, array, string */
  67.     char     *order_c;
  68.     char     sort_char,
  69.             *s;
  70.     NODE     *arr, *ind;
  71.     short        num_args, sort_type, in_reverse = 0;
  72.  
  73.     if ((num_args = b_get_three(tree, &t1, &t2, &t3)) < 3)
  74.         {
  75.         if (num_args == 2)
  76.             sort_type = ASCII_SORT;
  77.         else
  78.             fatal("sort requires at least two arguments");
  79.         }
  80.     else
  81.         {
  82.         order_c = force_string(t3)->stptr;
  83.         if (*order_c == 'r' || *order_c == 'R')
  84.             {
  85.             in_reverse = 1;
  86.             sort_char = *(order_c + 1);
  87.             }
  88.         else
  89.             sort_char = *order_c;
  90.         switch (sort_char)
  91.             {
  92.         case 'n':
  93.         case 'N':
  94.             sort_type = NUM_SORT;
  95.         break;
  96.         case 'd':
  97.         case 'D':
  98.             sort_type = DICT_SORT;
  99.         break;
  100.         case 'a':
  101.         case 'A':
  102.         default:
  103.             sort_type = ASCII_SORT;
  104.         break;
  105.             }
  106.         if (in_reverse)
  107.             ++sort_type;
  108.         free_temp(t3);
  109.         }
  110.     
  111.     arr = t1;
  112.     if (t1->type == Node_param_list)
  113.         arr = stack_ptr[t1->param_cnt];
  114.     if (arr->type != Node_var && arr->type != Node_var_array)
  115.         fatal("first argument of sort is not a variable");
  116.     
  117.     ind = t2;
  118.     if (t2->type == Node_param_list)
  119.         ind = stack_ptr[t2->param_cnt];
  120.     if (ind->type != Node_var && ind->type != Node_var_array)
  121.         fatal("second argument of sort is not a variable");
  122.     assoc_clear(ind);
  123.     return tmp_number((AWKNUM)
  124.         create_index_array(arr, ind, sort_type));
  125.     }
  126.  
  127. static NODE **stat_sorter;
  128.  
  129. /* loop over arr, copying index and element pointers; sort this
  130. temp array on values of elements, then use this order to create
  131. numerically-indexed ind array via 
  132.     *assoc_lookup(ind, tmp_number((AWKNUM) (number))) 
  133.         = make_string(ptr to index string, len of string);
  134. 1    hiccup results of assoc_scan of arr[] into temporary
  135.         handled array of NODE pointers
  136. 2    sort array of NODE pointers by element strings
  137. 3    walk sorted NODE pointers and create the array ind[] with
  138.         indexes 1: up and values equal to arr[] indexes
  139. 4    return number of elements in ind[]
  140.  
  141. Prelim version: walk array to precalculate size of sorter, then walk
  142. it again and fill in the buckets. Not a horrible waste of time.
  143. */
  144. static long create_index_array(NODE *arr, NODE *ind, short sort_type)
  145.     {
  146.     struct search *l;
  147.     long    j, k, numIndexes = 0;
  148.     
  149.     for (l = assoc_scan_sort(arr); l; l = assoc_next_sort((struct search *)l))
  150.         {
  151.         ++numIndexes;
  152.         }
  153.     if (numIndexes == 0)
  154.         return(0);
  155.     emalloc(stat_sorter, NODE **, (sizeof(NODE *) *
  156.         numIndexes), "create_index_array");
  157.     for (j = 0, l = assoc_scan_sort(arr); l; l = assoc_next_sort((struct search *)l), ++j)
  158.         {
  159.         if (sort_type >= NUM_SORT)
  160.             force_number(l->retval->ahvalue);
  161.         else
  162.             force_string(l->retval->ahvalue);
  163.         *(stat_sorter + j) = l->retval;
  164.         }
  165.     SortArray(numIndexes, sort_type);
  166.     for (j = 0, k = 1; j < numIndexes; ++j, ++k)
  167.         {
  168.         *assoc_lookup(ind, tmp_number((AWKNUM) (k))) 
  169.             = make_string((*(stat_sorter+j))->ahname->stptr,
  170.                 (*(stat_sorter+j))->ahname->stlen);
  171.         }
  172.     free(stat_sorter);
  173.     return(numIndexes);
  174.     }
  175.  
  176.  
  177. typedef short (*CompareFunction)(long lb, long ub);
  178. static CompareFunction compFuncArray[NUMSORTS];
  179. static CompareFunction compFunc;
  180.  
  181.  
  182. void InitCompFuncArray()
  183.     {
  184.     compFuncArray[0] = ASCIIComp;
  185.     compFuncArray[1] = RASCIIComp;
  186.     compFuncArray[2] = DictComp;
  187.     compFuncArray[3] = RDictComp;
  188.     compFuncArray[4] = NumComp;
  189.     compFuncArray[5] = RNumComp;
  190.     }
  191.  
  192. void SortArray(long numIndexes, short sort_type)
  193.     {
  194.     if (!(compFuncArray[0]))
  195.         InitCompFuncArray();
  196.     compFunc = compFuncArray[sort_type];
  197.     if (numIndexes)
  198.         qs(0L, numIndexes - 1L);
  199.     }
  200.  
  201. void qs(long lb, long ub)
  202.     {
  203.     long    j;
  204.     
  205.     if (lb < ub)
  206.         {
  207.         if (j = Rearrange(lb, ub))
  208.             qs(lb, j - 1L);
  209.         qs(j + 1L, ub);
  210.         }
  211.     }
  212.  
  213. long Rearrange(long lb, long ub)
  214.     {
  215.     do
  216.         {
  217.         while (ub > lb && compFunc(ub, lb) >= 0)
  218.             ub--;
  219.         if (ub != lb)
  220.             {
  221.             SwapSorters(ub, lb);
  222.             while (lb < ub && compFunc(lb, ub) <= 0)
  223.                 lb++;
  224.             if (lb != ub)
  225.                 SwapSorters(lb, ub);
  226.             }
  227.         } while (lb != ub);
  228.     return(lb);
  229.     }
  230.  
  231. void SwapSorters(long i, long j)
  232.     {
  233.     NODE    *temp = *(stat_sorter + i);
  234.     
  235.     *(stat_sorter + i) = *(stat_sorter + j);
  236.     *(stat_sorter + j) = temp;
  237.     }
  238.  
  239. /* Sort compare functions - ASCII, dictionary, numeric */
  240.  
  241. short ASCIIComp(long i, long j)
  242.     {
  243.     return(strcmp((*(stat_sorter + i))->ahvalue->stptr,
  244.         (*(stat_sorter + j))->ahvalue->stptr));
  245.     }
  246.  
  247. short RASCIIComp(long i, long j)
  248.     {
  249.     return(strcmp((*(stat_sorter + j))->ahvalue->stptr,
  250.         (*(stat_sorter + i))->ahvalue->stptr));
  251.     }
  252.  
  253. short DictComp(long i, long j)
  254.     {
  255.     return(PtrLenPtrLenCompare((*(stat_sorter + i))->ahvalue->stptr,
  256.     (*(stat_sorter + i))->ahvalue->stlen,
  257.     (*(stat_sorter + j))->ahvalue->stptr,
  258.     (*(stat_sorter + j))->ahvalue->stlen));
  259.     }
  260.  
  261. short RDictComp(long i, long j)
  262.     {
  263.     return(PtrLenPtrLenCompare((*(stat_sorter + j))->ahvalue->stptr,
  264.     (*(stat_sorter + j))->ahvalue->stlen,
  265.     (*(stat_sorter + i))->ahvalue->stptr,
  266.     (*(stat_sorter + i))->ahvalue->stlen));
  267.     }
  268.  
  269. short NumComp(long i, long j)
  270.     {
  271.     if ((*(stat_sorter + i))->ahvalue->numbr <
  272.         (*(stat_sorter + j))->ahvalue->numbr)
  273.         return(-1);
  274.     else if ((*(stat_sorter + i))->ahvalue->numbr ==
  275.         (*(stat_sorter + j))->ahvalue->numbr)
  276.         return(0);
  277.     else
  278.         return(1);
  279.     }
  280.  
  281. short RNumComp(long i, long j)
  282.     {
  283.     if ((*(stat_sorter + i))->ahvalue->numbr <
  284.         (*(stat_sorter + j))->ahvalue->numbr)
  285.         return(1);
  286.     else if ((*(stat_sorter + i))->ahvalue->numbr ==
  287.         (*(stat_sorter + j))->ahvalue->numbr)
  288.         return(0);
  289.     else
  290.         return(-1);
  291.     }
  292.  
  293. typedef Byte *BPtr;
  294. short PtrLenPtrLenCompare(Ptr spatPtr, short patLen, Ptr stargetPtr, short targetLen)
  295.     {
  296.     BPtr    patPtr = (BPtr)spatPtr,
  297.             patEndPtr = patPtr + patLen,
  298.             curPtr = (BPtr)stargetPtr,
  299.             curEndPtr = curPtr + targetLen;
  300.     short        i, j;
  301.     
  302.     while (patPtr < patEndPtr && curPtr < curEndPtr && *patPtr == *curPtr)
  303.         {
  304.         ++patPtr;
  305.         ++curPtr;
  306.         }
  307.     
  308.     if (patPtr == patEndPtr && curPtr == curEndPtr) /* exact match */
  309.         return(0);
  310.     if (patPtr == patEndPtr && curPtr != curEndPtr) /* pattern too short */
  311.         return(-1);
  312.     if (patPtr != patEndPtr && curPtr == curEndPtr) /* starget too short */
  313.         return(1);
  314.     
  315.     /* true miscompare within string */
  316.     i = (short)*patPtr;
  317.     j = (short)*curPtr;
  318.     /* sequence: nonalpha, AaBbCc...Zz */
  319.     /* 'A' = 65, 'a' = 97; move 'U' to 'U'*2 + 256, 'u' to 'u'*2 + 193 */
  320.     /* 'A' -> 386, 'B' -> 388, 'a' -> 387, 'b' -> 389 etc */
  321.     if ('A' <= i && i <= 'Z')
  322.         i = i*2 + 256;
  323.     else if ('a' <= i && i <= 'z')
  324.         i = i*2 + 193;
  325.     if ('A' <= j && j <= 'Z')
  326.         j = j*2 + 256;
  327.     else if ('a' <= j && j <= 'z')
  328.         j = j*2 + 193;
  329.     return(i - j);
  330.     }
  331.